// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

struct run {
  struct run *next;
};

// 一个空闲列表受到一个自旋锁保护
// 每个CPU维护一个自己的空闲页列表
// NCPU为CPU数目
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

// 初始化空闲列表
// xv6假设机器有128MB的RAM
void
kinit()
{
  // 初始化每个空闲页列表的锁，每个锁的名字都叫kmem
  for(int i=0; i<=NCPU-1; ++i)  initlock(&kmem[i].lock, "kmem");
  // 释放每一页内存
  freerange(end, (void*)PHYSTOP);
}

// 批量释放内存
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

//  将一个内存页面添加（push）到空闲列表上(头插法)
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
  struct run *r;

  // 不在机器RAM范围内（猜测）
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  // 首先将待释放内存中的每一个字节设置为1。这将导致使用释放后的内存的代码（使用“悬空引用”）读取到垃圾信息而不是旧的有效内容，从而希望这样的代码更快崩溃。
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  // 需要关中断才能获取cpu号
  push_off();
  // 获取当前cpu编号，获得对应的锁并修改对应的空闲内存表
  int cpu_id = cpuid();
  acquire(&kmem[cpu_id].lock);
  r->next = kmem[cpu_id].freelist;
  kmem[cpu_id].freelist = r;
  release(&kmem[cpu_id].lock);
  pop_off();
}

// 从空闲页表中取出一个页
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r;

  // 从当前cpu的空闲页表获取一个空闲页，如果当前cpu的空闲页表为空则调度其他cpu的空闲页
  push_off();
  int cpu_id = cpuid();
  acquire(&kmem[cpu_id].lock);
  r = kmem[cpu_id].freelist;
  // 当前cpu的页表尚有空闲页
  if(r) kmem[cpu_id].freelist = r->next;
  // 当前cpu页表暂无空闲页
  else{
    // 遍历其他cpu空闲页列表
    for(int i=0; i<=NCPU-1; ++i){
      // 跳过当前cpu
      if(i == cpu_id) continue;

      // 尝试在这个cpu的空闲页表里获取一个空闲页
      acquire(&kmem[i].lock);
      r = kmem[i].freelist;
      // 拿到了
      if(r){
        kmem[i].freelist = r->next;
        release(&kmem[i].lock);
        break;
      }
      release(&kmem[i].lock);
    }
  }
  release(&kmem[cpu_id].lock);
  pop_off();


  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}
